/* HashTableChained.java, adapted from HW6 */

package dict;
import list.*;

/**
 *  HashTableChained implements a Dictionary as a hash table with chaining.
 *  All objects used as keys must have a valid hashCode() method, which is
 *  used to determine which bucket of the hash table an entry is stored in.
 *  Each object's hashCode() is presumed to return an int between
 *  Integer.MIN_VALUE and Integer.MAX_VALUE.  The HashTableChained class
 *  implements only the compression function, which maps the hash code to
 *  a bucket in the table's range.
 *
 *  DO NOT CHANGE ANY PROTOTYPES IN THIS FILE.
 **/

public class HashTableChained implements Dictionary {

	/**
	 *  Place any data fields here.
	 **/
	private int size;	// Tracks number of elements in Dictionary.
	private SList[] table;

	/** 
	 *  Construct a new empty hash table intended to hold roughly sizeEstimate
	 *  entries.  (The precise number of buckets is up to you, but we recommend
	 *  you use a prime number, and shoot for a load factor between 0.5 and 1.)
	 **/

	public HashTableChained(int sizeEstimate) {
		// Your solution here.
		sizeEstimate = sizeEstimate * 5 / 4;
		while (!isPrime(sizeEstimate)) {
			sizeEstimate++;
		}
		resetTable(sizeEstimate);
	}

	/** 
	 *  Construct a new empty hash table with a default size.  Say, a prime in
	 *  the neighborhood of 100.
	 **/

	public HashTableChained() {
		// Your solution here.
		resetTable(101);
	}

	/**
	 *  Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE
	 *  to a value in the range 0...(size of hash table) - 1.
	 *
	 *  This function should have package protection (so we can test it), and
	 *  should be used by insert, find, and remove.
	 **/

	int compFunction(int code) {
		// Replace the following line with your solution.
		// return 88;
		return Math.abs(((20553 * code + 41) % 16908799) % table.length);
	}

	/**
	 * Checks to see whether a number n is prime.
	 * @param n is the number we want to determine is prime or not.
	 * @return true if prime, false if composite.
	 */
	private static boolean isPrime (int n) {
		for (int divisor = 2; divisor < n; divisor++) {
			if (n % divisor == 0) {
				return false;
			}
		}
		return true;
	}

	/** 
	 *  Returns the number of entries stored in the dictionary.  Entries with
	 *  the same key (or even the same key and value) each still count as
	 *  a separate entry.
	 *  @return number of entries in the dictionary.
	 **/

	public int size() {
		// Replace the following line with your solution.
		// return 0;
		return size;
	}

	/** 
	 *  Tests if the dictionary is empty.
	 *
	 *  @return true if the dictionary has no entries; false otherwise.
	 **/

	public boolean isEmpty() {
		// Replace the following line with your solution.
		// return true;
		if (size == 0) {
			return true;
		}
		return false;
	}

	/**
	 *  Create a new Entry object referencing the input key and associated value,
	 *  and insert the entry into the dictionary.  Return a reference to the new
	 *  entry.  Multiple entries with the same key (or even the same key and
	 *  value) can coexist in the dictionary.
	 *
	 *  This method should run in O(1) time if the number of collisions is small.
	 *
	 *  @param key the key by which the entry can be retrieved.
	 *  @param value an arbitrary object.
	 *  @return an entry containing the key and value.
	 **/

	public Entry insert(Object key, Object value) {
		// Replace the following line with your solution.
		// return null;
		Entry toInsert = new Entry();
		toInsert.key = key;
		toInsert.value = value;

		int index = compFunction(key.hashCode());
		table[index].insertBack(toInsert);

		size++;
		return toInsert;
	}

	/** 
	 *  Search for an entry with the specified key.  If such an entry is found,
	 *  return it; otherwise return null.  If several entries have the specified
	 *  key, choose one arbitrarily and return it.
	 *
	 *  This method should run in O(1) time if the number of collisions is small.
	 *
	 *  @param key the search key.
	 *  @return an entry containing the key and an associated value, or null if
	 *          no entry contains the specified key.
	 **/

	public Entry find(Object key) {
		// Replace the following line with your solution.
		// return null;
		int index = compFunction(key.hashCode());
		SListNode curr = (SListNode)(table[index].front());
		try {
			while (true) {
				if (((Entry)(curr.item())).key().equals(key)) {
					return (Entry)(curr.item());
				}
				curr = (SListNode)(curr.next());
			}
		} catch (InvalidNodeException e) {
			return null;
		}
	}

	/** 
	 *  Remove an entry with the specified key.  If such an entry is found,
	 *  remove it from the table and return it; otherwise return null.
	 *  If several entries have the specified key, choose one arbitrarily, then
	 *  remove and return it.
	 *
	 *  This method should run in O(1) time if the number of collisions is small.
	 *
	 *  @param key the search key.
	 *  @return an entry containing the key and an associated value, or null if
	 *          no entry contains the specified key.
	 */

	public Entry remove(Object key) {
		// Replace the following line with your solution.
		// return null;
		int index = compFunction(key.hashCode());
		SListNode curr = (SListNode)(table[index].front());
		try {
			while (true) {
				if (((Entry)(curr.item())).key().equals(key)) {
					Entry myEntry = ((Entry)(curr.item()));
					curr.remove();
					size--;
					return myEntry;
				}
				curr = (SListNode)(curr.next());
			}
		} catch (InvalidNodeException e) {
			return null;
		}
	}

	/**
	 *  Remove all entries from the dictionary.
	 */
	public void makeEmpty() {
		// Your solution here.
		resetTable(table.length);
	}
	
	/**
	 * resetTable() resets entire dictionary by reinitializing each element of table to an SList.
	 * @param size is the size of the table.
	 */
	private void resetTable(int initSize) {
		size = 0;
		table = new SList[initSize];
		for (int i = 0; i < table.length; i++) {
			table[i] = new SList();
		}
	}
	
	public void testCollisions() {
		int[] count = countCollisions();
		for (int i = 0; i < count.length; i++) {
			System.out.print("\nBucket: " + i + "\tCount: " + count[i] + "\t");
			for (int j = 0; j < count[i]; j++) {
				System.out.print("*");
			}
		}
	}
	
	private int[] countCollisions() {
		int[] count = new int[table.length];
		for (int i = 0; i < table.length; i++) {
			count[i] = table[i].length();
		}
		return count;
	}
	
	public static void main (String[] args) {
		System.out.println("\n== Testing insert() ==");
		HashTableChained myTable = new HashTableChained(5);
		myTable.insert(1, "One");
		myTable.insert(2, "Two");
		myTable.insert(3, "Three");
		myTable.insert(4, "Four");
		myTable.insert(5, "Five");
		myTable.insert(6, "Six");
		myTable.insert(7, "Seven");
		myTable.insert(8, "Eight");
		myTable.insert(9, "Nine");
		myTable.insert(10, "Ten");
		System.out.println("After inserting, myTable contains: ");
		for (int i = 0; i < myTable.table.length; i++) {
			System.out.println("Bucket: " + i + "\tContents: " + myTable.table[i]);
		}
		
		System.out.println("\n== Testing find() ==");
		System.out.println("myTable.find(1) should map to 'One': " + myTable.find(1).value());
		System.out.println("myTable.find(2) should map to 'Two': " + myTable.find(2).value());
		System.out.println("myTable.find(3) should map to 'Three': " + myTable.find(3).value());
		System.out.println("myTable.find(4) should map to 'Four': " + myTable.find(4).value());
		System.out.println("myTable.find(5) should map to 'Five': " + myTable.find(5).value());
		System.out.println("myTable.find(6) should map to 'Six': " + myTable.find(6).value());
		System.out.println("myTable.find(7) should map to 'Seven': " + myTable.find(7).value());
		System.out.println("myTable.find(8) should map to 'Eight': " + myTable.find(8).value());
		System.out.println("myTable.find(9) should map to 'Nine': " + myTable.find(9).value());
		System.out.println("myTable.find(10) should map to 'Ten': " + myTable.find(10).value());
		
		System.out.println("\n==Testing remove() ==");
		Entry removedNode;
		removedNode = myTable.remove(1);
		System.out.println("\nRemoved node: (" + removedNode.key() + ", " + removedNode.value() + ")");
		System.out.println("After myTable.remove(1), myTable contains: ");
		for (int i = 0; i < myTable.table.length; i++) {
			System.out.println("Bucket: " + i + "\tContents: " + myTable.table[i]);
		}
		System.out.println("Size should be 9: " + myTable.size);
		removedNode = myTable.remove(1);
		System.out.println("\nRemoved node: " + removedNode);
		System.out.println("After myTable.remove(1), myTable contains: ");
		for (int i = 0; i < myTable.table.length; i++) {
			System.out.println("Bucket: " + i + "\tContents: " + myTable.table[i]);
		}
		System.out.println("Size should be 9: " + myTable.size);
		removedNode = myTable.remove(8);
		System.out.println("\nRemoved node: (" + removedNode.key() + ", " + removedNode.value() + ")");
		System.out.println("After myTable.remove(8), myTable contains: ");
		for (int i = 0; i < myTable.table.length; i++) {
			System.out.println("Bucket: " + i + "\tContents: " + myTable.table[i]);
		}
		System.out.println("Size should be 8: " + myTable.size);
		removedNode = myTable.remove(8);
		System.out.println("\nRemoved node: " + removedNode);
		System.out.println("After myTable.remove(8), myTable contains: ");
		for (int i = 0; i < myTable.table.length; i++) {
			System.out.println("Bucket: " + i + "\tContents: " + myTable.table[i]);
		}
		System.out.println("Size should be 8: " + myTable.size);
		removedNode = myTable.remove(5);
		System.out.println("\nRemoved node: (" + removedNode.key() + ", " + removedNode.value() + ")");
		System.out.println("After myTable.remove(5), myTable contains: ");
		for (int i = 0; i < myTable.table.length; i++) {
			System.out.println("Bucket: " + i + "\tContents: " + myTable.table[i]);
		}
		System.out.println("Size should be 7: " + myTable.size);
		
	}

}
